package leetcode.D500.T416;

import java.lang.reflect.Array;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-21 12:46:03 星期一
 */

class Solution {
    /**
     * 一刷
     * 分析：
     *      从nums中找到两个子集的和相等，也就相当于从中找到一个子集，它的和是总和的一半，记为half
     *      nums中每个数都有 选/不选 两种状态，想到动态规划
     * 动态规划思路：
     *      1. dp[i][j]含义：在nums[0~i]中能否找到一个子集，它们的和为j
     *      2. 初始状态：dp[0][0]=true, dp[0][0<j<=half]=false,dp{~][0]=true
     *      3. 最终解：dp[nums.length][half]是否为true
     *      4. 状态转移：dp[i][j]可以根据选/不选nums[i-1]来求得
     *          3.1 不选，且dp[i-1][j]为true，则为true。含义：光在num[0~(i-1)]中就已经找到了和为j的子集
     *          3.2 选，且dp[i-1][j-nums[i-1]]为true，则为true。含义：略
     * 剪枝策略：
     *      1. 如果half为奇数，肯定是找不到的，返回false
     *      2. 遍历i时
     *          2.1 如果nums[i]>half，没必要继续找，因为肯定不会选nums[i]，不会影响dp，直接continue
     *          2.2 如果nums[i]==half，那么直接找到了{nums[i]}这个子集，返回true
     *      3. 遍历j时，可以用sum记录一下nums[0~(i-1)]的和，如果j>sum，超出了nums[0~(i-1)]的总和，肯定找不到了
     *      4. 如果某次遍历，出现了dp[i][half]为true，说明已经找到了某个子集的和为half，直接返回true
     * 空间复杂度优化：上述复杂度为O(m*n)，可以优化为O(n)。其中m=nums.length, n=half=1/2(sum)
     */
    /*public boolean canPartition(int[] nums) {
        int half = 0;
        for (int num : nums) {
            half += num;
        }
        if (half%2 != 0)
            return false;
        half /= 2;
        boolean[] dp = new boolean[half+1], temp = new boolean[half+1];
        dp[0] = true; temp[0] = true;
        int sum = 0;
        for(int i=0; i<nums.length; ++i) {
            if (nums[i] > half)
                continue;
            else if (nums[i] == half)
                return true;
            else {
                sum += nums[i];
                for(int j=1; j<=sum && j<=half; ++j) {
                    if (dp[j] || (j>=nums[i] && dp[j-nums[i]]))
                        temp[j] = true;
                }
                if (temp[half])
                    return true;
                System.arraycopy(temp, 0, dp, 0, temp.length);
            }
        }
        return false;
    }*/

    // 二刷
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i=0; i<nums.length; ++i)
            sum += nums[i];
        if (sum % 2 != 0)
            return false;
        int half = sum / 2;
        boolean[] dp = new boolean[half+1], temp = new boolean[half+1];
        dp[0] = true;
        sum = 0;
        for (int i=0; i<nums.length; ++i) {
            if (nums[i] > half)
                continue;
            if (nums[i] == half)
                return true;
            sum += nums[i];
            for (int j=0; j<=sum && j<=half; ++j) {
                if (dp[j] || (j >= nums[i] && dp[j-nums[i]]))
                    temp[j] = true;
            }
            if (temp[half])
                return true;
            System.arraycopy(temp, 0, dp, 0, temp.length);
        }
        return dp[half];
    }
}